Eleanore Semaphore

Eleanore Semaphore works in a darky corner of a small room with listings all around. Her system has evolved greatly since last year, though all she can show you is still the same: bunches of A and B displayed in no-obvious-order on a text console and that she controls with magic key combos. Hear her talking about how she implemented components programming, auto-dependencies resolving and virtual clock algorithm for her scheduler. Maybe you prefer a different style.

The foundation of a kernel

Ok, so you know what a semaphore is? Or maybe monitors or just plain message passing would be a better way to synchronize? 'Cos I guess we want to synchronize our processes. You want to write a µ-kernel don't you, even if you actually wanted to run some tasks in the kernel for performance later?

Honestly, if you are like Eleanore, you probably have a pretty good idea of what you want the "big picture" to feel like, but little idea of how to get there. In fact, you'll probably be reading research papers pretty soon, so maybe the real answer hasn't been invented yet? And whether you are going to write just a barebones microkernel with the most simple possible IPC system, or a sophisticated distributed RPC model with garbage collected components, you are going to need some basics first.

And we are going to dive straight into the theory, but I guess that won't scare you, right?

Threads, and maybe processes

We are going to be multi-threading, right? So we need threads. Personally I'd start from the basic threads, because lots of ofter stuff depends on them. You don't need to actually do any multi-threading in your kernel, but that might be the easiest thing. In any case, you probably want some kind of scheduler in your kernel. At least enough that you can tell a blocked thread from a ready-to-run thread.

Whether you really want processes at this point depends. The simple thing to do is to make them just some dummy object at this point, and flesh them out when virtual memory management is implemented.

Synchronization

You will then need some kind of syncronization primitives; probably at least some kind of semaphores. And while you can definitely get mutual exclusion with nothing but spinlocks, you need a scheduler so that you can make your threads blocked, so you don't need to busy-loop.

And once we have synchronization in place, we are ready to start printing As and Bs in a predictable order, right?

Userspace

Since a µ-kernel is nothing without userspace processes, you probably want to go into userspace relatively early. You could simulate them in kernel of course, and you can load them using GRUB or whatever you load your kernel with. But for real userspace you need two things. And you could do them in any order really.

And really, if you are like me, then you probably agree that these two are what makes an operating system different.

Virtual memory management

You probably need a manager for virtual memory and this is a good moment to design one. You have several options, like always:

write a normal VMM in kernel
write only the minimum in kernel, and support either:
- separate pagers in userspace, or
- self-paging

If you are going to support some kinds of userspace management (and even if you don't), you should probably consider how your IPC and VMM will interact before you start writing any high-level management code. But then again, most existing systems seem to be quite happy with a "regular" VMM.

Existing virtual memory management schemes that you might find useful include those in Unix, including Linux, FreeBSD and others, VMS, Windows NT (and VMS and NT similarities), Mach (and Darwin), L4, Nemesis (PDF).

ToDo: should this stuff go to a separate "Virtual Memory" page?

How can my processes talk to each other?

For any future processes to be able to talk to each other (and eventually outside world) one needs some facilities for communication. What kind of you are going to have, depends on what exactly do you want your system to feel like, but you definitely want something. Some of the alternatives available are

Unix style: pipes, sockets, files, select
Message Passing, or maybe Remote Procedure Calls
Shared Memory
maybe something totally new?

There are almost endless number of different possibilities and several variations of each.

Eleanore's Bookshelf

Well, most of these aren't books, actually. More likely the proceedings of USENIX or Hot Topics in Operating Systems, stacks of printed articles from various universities ... She also has most of Andy's writings and will brew him a cup of fresh coffee when Linus comes back for the debates.